// 438.找到字符串中所有字母异位词

package LeetcodeHot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution438 {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if(s.length() < p.length())
            return result;
        // 分别存储 26 个字母的个数
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        // 先对最开始的子串进行计数
        for (int i = 0; i < p.length(); i++) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }
        if (Arrays.equals(sCount, pCount))
            result.add(0);
        // 遍历后续子串
        for (int i = 1; i <= s.length() - p.length(); i++) {
            --sCount[s.charAt(i - 1) - 'a'];
            ++sCount[s.charAt(i + p.length() - 1) - 'a'];
            if (Arrays.equals(sCount, pCount))
                result.add(i);
        }
        return result;
    }
}
